1. Field of the Invention
The present invention relates to computer systems and methods in which data resources are shared among concurrent data consumers while preserving data integrity and consistency relative to each consumer. More particularly, the invention concerns a concurrency mechanism known as transactional memory.
2. Description of the Prior Art
By way of background, transactional memory (TM) can be implemented in either hardware or software. Although both approaches are viable candidates for use in the design and construction of shared-memory parallel software, hardware transactional memory (HTM) operates more efficiently than software transactional memory (STM). On other hand, with the exception of certain research prototypes that are not currently practical for production use, HTM's small transactional memory size (the classic example being an L1 cache) imposes limitations on the amount of data that can participate in a given transaction as well as the types of operations that may be performed within a transaction. Consequently, small memory HTM is not generally suitable for accessing large data structures.
There are many schemes for extending the reach of HTM to handle larger transactions. Most involve best effort approach wherein HTM transaction processing is used if possible, but with a software-based fallback option being provided (such as reverting to locking or STM) in the event of HTM failure. These hybrid schemes have drawbacks such as reduced concurrency, increased overhead, and increased complexity, particularly in retry/contention-manager semantics.
There is a need for a mechanism that permits limited size HTM implementations to perform small memory manipulations on unbounded multi-linked lists or other arbitrarily large data structures, in order to gain the benefits of HTM, while either eliminating or reducing the severity of the drawbacks normally associated with use of HTM on such data.